package Array.easy;

import java.util.HashMap;

/**
 * 1. 问题描述
 *      假设现在有一个存储字符串的数组 words 和 一个字典字符串 chars
 *      我们需要利用chars中的字符平凑出words中的单词，注意每个字符只能
 *      用一次，如果可以平凑出来，说明这个单词我们掌握了，求出最终我们能
 *      掌握的所有单词的长度
 *
 * 2，算法分析
 *      1. 考虑如何判断单个元素的情况，然后遍历words中的每一个进行判断即可
 *          对于单个元素，我们采用hashmap统计chars中每个字符出现的次数，然后
 *          扫描word，即可
 *          时间复杂度和空间复杂度都比较高，每一轮的时间复杂度为O(2n),一共n轮
 *          所以总的时间复杂度为O(2n^2)
 *          然后每轮我们都需要创建一个长度为chars.len的hash表，总的空间复杂度
 *          为O(n^2)
 *
 *      2. 优化上述实现 实际上上述出现了许多冗余的操作，比如重复对同一个字符创建相同的hashmap
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 拼写单词 {
    public static void main(String[] args) {
        String[] words = {
                "dyiclysmffuhibgfvapygkorkqllqlvokosagyelotobicwcmebnpznjbirzrzsrtzjxhsfpiwyfhzyonmuabtlwin","ndqeyhhcquplmznwslewjzuyfgklssvkqxmqjpwhrshycmvrb","ulrrbpspyudncdlbkxkrqpivfftrggemkpyjl","boygirdlggnh","xmqohbyqwagkjzpyawsydmdaattthmuvjbzwpyopyafphx","nulvimegcsiwvhwuiyednoxpugfeimnnyeoczuzxgxbqjvegcxeqnjbwnbvowastqhojepisusvsidhqmszbrnynkyop","hiefuovybkpgzygprmndrkyspoiyapdwkxebgsmodhzpx","juldqdzeskpffaoqcyyxiqqowsalqumddcufhouhrskozhlmobiwzxnhdkidr","lnnvsdcrvzfmrvurucrzlfyigcycffpiuoo","oxgaskztzroxuntiwlfyufddl","tfspedteabxatkaypitjfkhkkigdwdkctqbczcugripkgcyfezpuklfqfcsccboarbfbjfrkxp","qnagrpfzlyrouolqquytwnwnsqnmuzphne","eeilfdaookieawrrbvtnqfzcricvhpiv","sisvsjzyrbdsjcwwygdnxcjhzhsxhpceqz","yhouqhjevqxtecomahbwoptzlkyvjexhzcbccusbjjdgcfzlkoqwiwue","hwxxighzvceaplsycajkhynkhzkwkouszwaiuzqcleyflqrxgjsvlegvupzqijbornbfwpefhxekgpuvgiyeudhncv","cpwcjwgbcquirnsazumgjjcltitmeyfaudbnbqhflvecjsupjmgwfbjo","teyygdmmyadppuopvqdodaczob","qaeowuwqsqffvibrtxnjnzvzuuonrkwpysyxvkijemmpdmtnqxwekbpfzs","qqxpxpmemkldghbmbyxpkwgkaykaerhmwwjonrhcsubchs"
        };
        String chars = "usdruypficfbpfbivlrhutcgvyjenlxzeovdyjtgvvfdjzcmikjraspdfp";
        for(String word : words) {
            if (isCompared2(word,chars)) {
                System.out.println(word);
            }
        }
    }

    public static int countCharacters1(String[] words, String chars) {
        int count = 0; // 记录最终掌握的单词总长度
        for(String word : words) {
            if(isCompared2(word,chars)) {
                count += word.length();
            }
        }
        return count;
    }


    public static int countCharacters2(String[] words, String chars) {
        HashMap<Character,Integer> map = new HashMap<>();
        int count = 0;
        for (int i = 0; i < chars.length(); i++) {
            if (map.containsKey(chars.charAt(i))) {
                map.put(chars.charAt(i),map.get(chars.charAt(i))+1);
            } else {
                map.put(chars.charAt(i),1);
            }
        }
        return count;
    }
    /**
     * 判断word是否可以由target中的字符生成
     *
     * hashmap法
     *
     * @param word
     * @param target
     * @return
     */
    public static boolean isCompared2(String word,String target) {
        if(word.length() > target.length()) {return false;}
        HashMap<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < target.length(); i++) {
            if (map.containsKey(target.charAt(i))) {
                map.put(target.charAt(i),map.get(target.charAt(i))+1);
            } else {
                map.put(target.charAt(i),1);
            }
        }
        for (int i = 0; i < word.length(); i++) {
            if (!map.containsKey(word.charAt(i))) {
                return false;
            }
            if (map.containsKey(word.charAt(i)) && map.get(word.charAt(i)) == 0) {
                return false;
            }
            if (map.containsKey(word.charAt(i)) && map.get(word.charAt(i)) != 0) {
                map.put(word.charAt(i),map.get(word.charAt(i))-1);
            }
        }
        return true;
    }

    /**
     * 利用int[] arr 来计数
     * 之前遇到过多次类的方式求解的问题
     * 相比于hashmap，速度快很多，因为hashmap底层需要判断hash冲突还有扩容等问题
     * 而int[]不需要，所以总体的时间要快很多
     * @param word
     * @param chars
     * @return
     */
    public static boolean isCompared3(String word,String chars) {
        int[] counter = new int[26]; // 计数器
        for(int i = 0; i < chars.length(); i++) {
            counter[chars.charAt(i) - 'a']++;
        }
        for(int i = 0; i < word.length(); i++) {
            if(counter[word.charAt(i)-'a'] == 0) {
                return false;
            }
            counter[word.charAt(i)-'a']--;
        }
        return true;
    }


}
